<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  <meta http-equiv="X-UA-Compatible" content="IE=edge" >
  <title>算法-二分查找 | BoBo&#39;Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="1、二分查找假设要在电话簿中找一个名字以K打头的人，可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做， 而是从中间开始，因为你知道以K打头的名字在电话簿中间。又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。 现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户 名为karlmageddo">
<meta property="og:type" content="article">
<meta property="og:title" content="算法-二分查找">
<meta property="og:url" content="https://www.boboios.cn/2019/03/05/%E7%AE%97%E6%B3%95-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/index.html">
<meta property="og:site_name" content="BoBo&#39;Blog">
<meta property="og:description" content="1、二分查找假设要在电话簿中找一个名字以K打头的人，可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做， 而是从中间开始，因为你知道以K打头的名字在电话簿中间。又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。 现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户 名为karlmageddo">
<meta property="article:published_time" content="2019-03-05T15:17:57.000Z">
<meta property="article:modified_time" content="2020-11-05T16:19:14.510Z">
<meta property="article:author" content="Lv Bo">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
  
    <link rel="alternative" href="/atom.xml" title="BoBo&#39;Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
  <div id="container">
    <div class="left-col">
    <div class="overlay"></div>
<div class="intrude-less">
	<header id="header" class="inner">
		<a href="/" class="profilepic">
			
			<img lazy-src="https://gitee.com/lvboios/PictureBed/raw/master/uPic/IMG_1199.JPG" class="js-avatar">
			
		</a>

		<hgroup>
		  <h1 class="header-author"><a href="/">Lv Bo</a></h1>
		</hgroup>

		
		<p class="header-subtitle">Your name my heart</p>
		

		
			<div class="switch-btn">
				<div class="icon">
					<div class="icon-ctn">
						<div class="icon-wrap icon-house" data-idx="0">
							<div class="birdhouse"></div>
							<div class="birdhouse_holes"></div>
						</div>
						<div class="icon-wrap icon-ribbon hide" data-idx="1">
							<div class="ribbon"></div>
						</div>
						
						
						<div class="icon-wrap icon-me hide" data-idx="3">
							<div class="user"></div>
							<div class="shoulder"></div>
						</div>
						
					</div>
					
				</div>
				<div class="tips-box hide">
					<div class="tips-arrow"></div>
					<ul class="tips-inner">
						<li>菜单</li>
						<li>标签</li>
						
						
						<li>关于我</li>
						
					</ul>
				</div>
			</div>
		

		<div class="switch-area">
			<div class="switch-wrap">
				<section class="switch-part switch-part1">
					<nav class="header-menu">
						<ul>
						
							<li><a href="/">主页</a></li>
				        
							<li><a href="/archives">所有文章</a></li>
				        
						</ul>
					</nav>
					<nav class="header-nav">
						<div class="social">
							
								<a class="github" target="_blank" href="https://github.com/BoBoMoon" title="github">github</a>
					        
						</div>
					</nav>
				</section>
				
				
				<section class="switch-part switch-part2">
					<div class="widget tagcloud" id="js-tagcloud">
						<a href="/tags/Flutter/" style="font-size: 10px;">Flutter</a> <a href="/tags/app%E5%AE%89%E5%85%A8/" style="font-size: 10px;">app安全</a> <a href="/tags/iOS%E6%8A%80%E5%B7%A7/" style="font-size: 20px;">iOS技巧</a> <a href="/tags/iOS%E7%9F%A5%E8%AF%86%E5%8F%8A%E5%8E%9F%E7%90%86/" style="font-size: 15px;">iOS知识及原理</a> <a href="/tags/%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80/" style="font-size: 10px;">其他语言</a> <a href="/tags/%E5%91%A8%E8%BE%B9%E8%BD%AF%E4%BB%B6/" style="font-size: 10px;">周边软件</a> <a href="/tags/%E5%BC%80%E5%8F%91%E6%95%88%E7%8E%87/" style="font-size: 10px;">开发效率</a> <a href="/tags/%E5%BF%83%E5%BE%97%E4%BD%93%E4%BC%9A/" style="font-size: 10px;">心得体会</a> <a href="/tags/%E7%AE%97%E6%B3%95/" style="font-size: 10px;">算法</a> <a href="/tags/%E8%A3%85%E9%80%BC%E4%B8%93%E7%94%A8/" style="font-size: 10px;">装逼专用</a>
					</div>
				</section>
				
				
				

				
				
				<section class="switch-part switch-part3">
				
					<div id="js-aboutme">莫疑春归无觅处，静待花开会有时</div>
				</section>
				
			</div>
		</div>
	</header>				
</div>

    </div>
    <div class="mid-col">
      <nav id="mobile-nav">
  	<div class="overlay">
  		<div class="slider-trigger"></div>
  		<h1 class="header-author js-mobile-header hide">Lv Bo</h1>
  	</div>
	<div class="intrude-less">
		<header id="header" class="inner">
			<div class="profilepic">
			
				<img lazy-src="https://gitee.com/lvboios/PictureBed/raw/master/uPic/IMG_1199.JPG" class="js-avatar">
			
			</div>
			<hgroup>
			  <h1 class="header-author">Lv Bo</h1>
			</hgroup>
			
			<p class="header-subtitle">Your name my heart</p>
			
			<nav class="header-menu">
				<ul>
				
					<li><a href="/">主页</a></li>
		        
					<li><a href="/archives">所有文章</a></li>
		        
		        <div class="clearfix"></div>
				</ul>
			</nav>
			<nav class="header-nav">
				<div class="social">
					
						<a class="github" target="_blank" href="https://github.com/BoBoMoon" title="github">github</a>
			        
				</div>
			</nav>
		</header>				
	</div>
</nav>

      <div class="body-wrap"><article id="post-算法-二分查找" class="article article-type-post" itemscope itemprop="blogPost">
  
    <div class="article-meta">
      <a href="/2019/03/05/%E7%AE%97%E6%B3%95-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/" class="article-date">
  	<time datetime="2019-03-05T15:17:57.000Z" itemprop="datePublished">2019-03-05</time>
</a>
    </div>
  
  <div class="article-inner">
    
      <input type="hidden" class="isFancy" />
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      算法-二分查找
    </h1>
  

      </header>
      
      <div class="article-info article-info-post">
        
	<div class="article-tag tagcloud">
		<ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li></ul>
	</div>

        

        <div class="clearfix"></div>
      </div>
      
    
    <div class="article-entry" itemprop="articleBody">
      
        <h4 id="1、二分查找"><a href="#1、二分查找" class="headerlink" title="1、二分查找"></a>1、二分查找</h4><p>假设要在电话簿中找一个名字以K打头的人，可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做， 而是从中间开始，因为你知道以K打头的名字在电话簿中间。又假设要在字典中找一个以O打头的单词，你也将从中间附近开始。</p>
<p>现在假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户 名为karlmageddon，Facebook可从以A打头的部分开始查找，但更合乎 逻辑的做法是从中间开始查找。<br>这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问 题，这种算法就是二分查找。<a id="more"></a></p>
<p>二分查找是一种算法，其输入是一个<strong>有序的</strong>元素列表。如果要查找的元素包含在列表中，二分查找返回其位置; 否则返回null。</p>
<p>下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字。<br>你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、 大了或对了。<br>假设你从1开始依次往上猜，这是简单查找 ，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到!</p>
<h4 id="2、更佳的查找方式"><a href="#2、更佳的查找方式" class="headerlink" title="2、更佳的查找方式"></a>2、更佳的查找方式</h4><p>下面是一种更佳的猜法。从50开始。<br>小了，但排除了一半的数字!至此，你知道1~50都小了。接下来，你猜75。大了，那余下的数字又排除了一半!使用二分查找时，你猜测的是中间 的数字，从而每次都将余下的数字排除一半。接下来，你猜63(50和75 中间的数字)。</p>
<p>这就是二分查找，不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字!</p>
<p>假设你要在字典中查找一个单词，而该字典包含240000个单词，你认为每种查找最多需要多少步<br>如果要查找的单词位于字典末尾，使用简单查找将需要240000步。使用二分查找时，每次排除一半单词，直到最后只剩下一个单词。因此，使用二分查找只需18步——少多了!一般而言，对于包含n个元素的列表，用二分查找最多需要 log<sub>2</sub>n 步，而简单查找最多需要n步。</p>
<p><strong>对数</strong></p>
<p>你可能不记得什么是对数了，但很可能记得什么是幂。log<sub>10</sub>100相<br>当于问“将多少个10相乘的结果为100”。答案是两个:10 × 10 = 100。因此，log<sub>10</sub>100 = 2。对数运算是幂运算的逆运算。</p>

      
    </div>
    
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/08/14/Flutter%E5%AE%89%E8%A3%85%E8%B8%A9%E5%9D%91%E8%AE%B0%E5%BD%95MacOS/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption"><</strong>
      <div class="article-nav-title">
        
          Flutter安装踩坑记录MacOS
        
      </div>
    </a>
  
  
    <a href="/2019/02/25/%E9%AB%98%E6%95%88%E5%AD%A6%E4%B9%A0%20%E7%AB%AF%E6%AD%A3%E5%AD%A6%E4%B9%A0%E6%80%81%E5%BA%A6/" id="article-nav-older" class="article-nav-link-wrap">
      <div class="article-nav-title">高效学习：端正学习态度</div>
      <strong class="article-nav-caption">></strong>
    </a>
  
</nav>

  
</article>


<div class="share_jia">
	<!-- JiaThis Button BEGIN -->
	<div class="jiathis_style">
		<span class="jiathis_txt">分享到: &nbsp; </span>
		<a class="jiathis_button_facebook"></a> 
    <a class="jiathis_button_twitter"></a>
    <a class="jiathis_button_plus"></a> 
    <a class="jiathis_button_tsina"></a>
		<a class="jiathis_button_cqq"></a>
		<a class="jiathis_button_douban"></a>
		<a class="jiathis_button_weixin"></a>
		<a class="jiathis_button_tumblr"></a>
    <a href="http://www.jiathis.com/share" class="jiathis jiathis_txt jtico jtico_jiathis" target="_blank"></a>
	</div>
	<script type="text/javascript" src="http://v3.jiathis.com/code/jia.js?uid=1405949716054953" charset="utf-8"></script>
	<!-- JiaThis Button END -->
</div>






<div class="duoshuo">
	<!-- 多说评论框 start -->
	<div class="ds-thread" data-thread-key="算法-二分查找" data-title="算法-二分查找" data-url="https://www.boboios.cn/2019/03/05/%E7%AE%97%E6%B3%95-%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/"></div>
	<!-- 多说评论框 end -->
	<!-- 多说公共JS代码 start (一个网页只需插入一次) -->
	<script type="text/javascript">
	var duoshuoQuery = {short_name:"lvboios"};
	(function() {
		var ds = document.createElement('script');
		ds.type = 'text/javascript';ds.async = true;
		ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
		ds.charset = 'UTF-8';
		(document.getElementsByTagName('head')[0] 
		 || document.getElementsByTagName('body')[0]).appendChild(ds);
	})();
	</script>
	<!-- 多说公共JS代码 end -->
</div>




</div>
      <footer id="footer">
  <div class="outer">
    <div id="footer-info">
    	<div class="footer-left”>
    		&copy; 2020 Lv Bo
    	</div>
      	<div class="footer-right">
      		<a href="http://hexo.io/" target="_blank">Hexo</a>  Theme <a href="https://github.com/litten/hexo-theme-yilia" target="_blank">Yilia</a> by Litten
      	</div>
    </div>
  </div>
</footer>
    </div>
    
  
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">



<script>
	var yiliaConfig = {
		fancybox: true,
		mathjax: true,
		animate: true,
		isHome: false,
		isPost: true,
		isArchive: false,
		isTag: false,
		isCategory: false,
		open_in_new: false
	}
</script>

<script src="http://7.url.cn/edu/jslib/comb/require-2.1.6,jquery-1.9.1.min.js"></script>


<script src="/js/main.js"></script>







<script type="text/x-mathjax-config">
MathJax.Hub.Config({
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    }
});

MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';                 
    }       
});
</script>

<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>


  </div>
</body>
</html>